/*
 * @lc app=leetcode.cn id=236 lang=java
 *
 * [236] 二叉树的最近公共祖先
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {


    TreeNode ans;

    Solution() {
        ans = null;
    }

    private boolean helper(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null)
            return false;
        
        boolean lson = helper(root.left, p, q);
        boolean rson = helper(root.right, p, q);

        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        }

        return lson || rson || root.val == p.val || root.val == q.val;

    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        helper(root, p, q);
        return ans;
    }
}
// @lc code=end

